#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

using ll = long long;
using db = double;
using vec = vector<int>;
using pii = pair<int,int>;

int read() {
    int x = 0,sgn = 1;char ch = getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*sgn;
}

const int N = 1e5 + 10;

char s[N],rt;
int cnt[500],n;

void solve() {
	scanf("%s",s + 1); n = strlen(s + 1);
	for(int c = 'a';c <= 'z';c++) cnt[c] = 0;
	for(int i = 1;i <= n;i++) cnt[s[i]]++;
	vector < char > pot;
	for(int c = 'a';c <= 'z';c++)
		if(cnt[c]) pot.pb(c);
	if(pot.size() == 1) { printf("%s\n",s + 1); return; }
	char fl = 0; for(auto c : pot) if(cnt[c] == 1) { fl = c; break; }
	if(fl > 0) {
		putchar(fl);
		for(int c = 'a';c <= 'z';c++)
			if(c != fl) {
				for(int i = 1;i <= cnt[c];i++) putchar(c);
			}
		puts(""); return;
	}
	char a = pot[0],b = pot[1];
	if(cnt[a] <= n / 2 + 1) {
		vector < char > dir;
		putchar(a); putchar(a); for(int i = 1;i <= n;i++) if(s[i] != a) dir.pb(s[i]);
		sort(dir.begin(),dir.end(),greater<char>());
		for(int i = 1;i <= cnt[a] - 2;i++) { putchar(dir.back()); dir.pop_back(); putchar(a); }
		while(dir.size()) putchar(dir.back()),dir.pop_back();
	} else {
		if(pot.size() == 2) {
			putchar(a); for(int i = 1;i <= cnt[b];i++) putchar(b); for(int i = 1;i < cnt[a];i++) putchar(a);
		} else {
			putchar(a); putchar(b); cnt[b]--; char c = pot[2];
			for(int i = 1;i < cnt[a];i++) putchar(a); putchar(c); cnt[c]--;
			for(char dit = a + 1;dit <= 'z';dit++) while(cnt[dit] > 0) putchar(dit),cnt[dit]--;
		}
	}
	puts("");
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    for(int t = in;t;t--) solve();
    return 0;
}
